# 动态规划：和递归有点像，看知乎的那篇文章。以前学过

# coinValueList: 存储钱的面值
# change：要找的钱
# 代码简单，但是需要太多次递归了
def recMC(coinValueList,change):
    minCoins = change   # 赋予结果初始值，假设最小面值是1了
    if change in coinValueList: # 一个就ok
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList,change-i)
            if numCoins < minCoins:
                print(i)
                minCoins = numCoins
    return minCoins
'''
    分析：上面的复杂性太大，他是一个从上向下的递归过程，会出现重复计算，比如：
        63--》1 + 1 + 1 + 1 + 1 + 58(递归下来就是需要对58进行递归求他的最小值了)
        63-->5 + 58(接下来依然需要对58进行递归求他的最小值了)
        也就是说我们会出现很多次递归重复计算的情况，启示本来我们只需要递归计算0-63个数的，但是这样就是很多中间的重复计算了。现在我们可以考虑记录下
        结果，也就是说我们建立一个64长度的列表，当58已经递归算出最小的值之后存到对应位置，以后递归先查看这个位置是否有值，有i的话就i不用递归了
'''
# 这下速度快多了
def recDC(coinValueList,change,knowResult):
    minCoins = change
    if change in coinValueList:
        return 1
    elif knowResult[change] > 0:
        return knowResult[change]

    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recDC(coinValueList,change - i,knowResult)
            if minCoins > numCoins:
                minCoins = numCoins
                knowResult[change] = minCoins
    return minCoins

'''
    分析：但是吧上面的东西不一定是最好的，这种东西用动态规划比较好一些，递归这种东西比较烦的就是不容易打印出详细的结果信息。
    因此下面准备认真考虑一下学习动态规划，动态规划的典型特点是求取最优解问题.多做题就好啦
'''
# coinValueList:有效硬币值的列表
# change：要求的找零值
# minCoins：包含每个值所需最小硬币数量的列表。当函数完成时，minCoins将包含0-找零值的所有值的解

'''
    现在我们想办法获得每个change的具体值应该是多少。比如要保留6的值是多少？
    思路：我们现在考虑存储每个change要使用的最大的硬币面值，比如6存储的是5，6-5=1.说明去掉这个最大的change = 1，然后我们有又知道change = 1的最大面值
    这样一直到0
'''
def dpMakeChange(coinValueList,change,minCoins,coinUsed):
    for cents in range(change+1):   # 硬币从0开始增加
        coinCount = cents
        newcoin = 1
        for j in [i for i in coinValueList if i <= cents]:  # 遍历可用的硬币面值,比cent小的面值前面已经计算了，这里面0的结果是0，不进入循环
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newcoin = j
        minCoins[cents] = coinCount
        coinUsed[cents] = newcoin
    return minCoins[change]

def printCoins(coinUsed,change):
    coin = change
    while coin > 0:
        thisCoin = coinUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin


def test():
    amnt = 63
    coinlist = [1,5,10,21,25]
    coinsUsed = [0]*(amnt+1)
    coinCount = [0]*(amnt+1)

    print("Making change for",amnt,"requires")
    print(dpMakeChange(coinlist,amnt,coinCount,coinsUsed),"coins")
    print("They are:")
    printCoins(coinsUsed,amnt)
    print("The used list is as follows:")
    print(coinsUsed)

if __name__ == '__main__':
    # print(recDC([1,5,10,25],63,[0]*64))
    # print(dpMakeChange([1, 5, 10, 25], 63,[0]*64),[0]*64)
    test()